#include <vector>
#include <unordered_map>

using namespace std;

// 使数组和能被P整除
// 给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空）
// 使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。
// 请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。
// 子数组 定义为原数组中连续的一组元素。
// 测试链接 : https://leetcode.cn/problems/make-sum-divisible-by-p/

class Solution 
{
public:
    int minSubarray(vector<int>& nums, int p) 
    {
        int mod = 0; // 整体余数
        for(int x : nums) mod = (mod + x) % p;
        if(mod == 0) return 0;

        int n = nums.size(), ans = n;
        // key : 前缀和 %p 的余数
		// value : 最晚出现的位置
        unordered_map<int, int> m;
        m[0] = -1;
        for(int i = 0, cur = 0, find; i < n; ++i)
        {
			// 0...i 这部分的余数
            cur = (cur + nums[i]) % p; 
            find = cur >= mod ? (cur - mod) : (cur + p - mod);
            // find = (cur + p - mod) % p;
            if(m.count(find)) ans = min(ans, i - m[find]);
            m[cur] = i;
        }

        return ans == n ? -1 : ans;
    }
};